/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-01-29
 * Time: 19:25
 */
public class Sort {
    // 冒泡排序
public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
        boolean flg=true;
        for (int j = 0; j < array.length-1-i ; j++) {
            if(array[j]>array[j+1]){
                int tmp=array[j];
                array[j]=array[j+1];
                array[j+1]=tmp;
                flg=false;
            }
        }
        if(flg==true){
            break;
        }
    }

    }

// 快速排序
public static void quickSort(int[] array){
    int left=0;
    int right=array.length-1;
    quick(array,left,right);
}
public static void quick(int[] array,int left,int right){
    if(left>=right){
        return;
    }

    int mid=findMid(array,left,right);
    swap(array,left,mid);
    int privot=func2(array,left,right);
    quick(array,left,privot-1);
    quick(array,privot+1,right);
}
    private static int func(int[] array,int left,int right){
        int tmp=array[left];
        int i=left;
        while(left<right){
        while(left<right && array[right]>=tmp){
            right--;
        }
        while(left<right&&array[left]<=tmp){
            left++;
        }
        if(left<right){
            swap(array,left,right);
        }

    }
    swap(array,i,left);
    return left;
    }
    private static  void swap(int[] array,int left,int right){
    int tmp=array[left];
    array[left]=array[right];
    array[right]=tmp;
    }
    private static int findMid(int[] array,int left,int right){
    int mid=left+(right-left)/2;
    if(array[left]>array[right]){
        if(array[mid]>array[left]){
            return left;
        }else if(array[mid]<array[right]){
            return right;
        }else{
            return mid;
        }

    }else{
        if(array[mid]>array[right]){
            return right;
        }else if(array[mid]<array[left]){
            return left;
        }else{
            return mid;
        }
    }
}
    public static int  func2(int[] array,int left,int right){
    int tmp=array[left];
    while(left<right){
        while(left<right&&array[right]>=tmp){
            right--;

        }
        if(left<right){
            array[left]=array[right];
        }
        array[left]=array[right];
        while(left<right&&array[left]<=tmp){
            left++;
        }
        if(left<right){
            array[right]=array[left];
        }

    }
    array[left]=tmp;

    return left;
    }
}

